package com.sunny.example.dynamicschedule;

import java.util.Scanner;

/**
 * 求最长子串
 *
 * 采用动态规划来实现：
 * 比如输入的1,3,2,4,2作为列
 * 行遍历次数从输入的正整数个数
 * 二维数组初始化时，每一行的值为输入的1,3,2,4,2的值。
 *
 * 计算最长子串和等于target的公式为：
 * dp[x][x] = dp[x-1][x] + dp[x-1][x-1]
 *
 */
public class DS3 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            String str = scanner.nextLine();
            int target = Integer.parseInt(scanner.nextLine());
            String[] strs = str.split(",");
            int len = strs.length;
            int maxLen = -1;
            int[][] dp = new int[len][len];
            //二维数组初始化
            for (int i = 0; i < len; i++) {//行
                for (int j = 0; j < len; j++) {//列
                    dp[i][j] = Integer.parseInt(strs[j]);
                }
            }

            int temp = Integer.parseInt(strs[0]);//初始化
            for (int k = 1; k < len; k++) {
                int y = k;

                dp[k][y] = dp[k - 1][y] + dp[k - 1][y - 1];
                temp = dp[k][y];
//                System.out.println("temp:"+temp);
                if (temp == target) {
                    maxLen = Math.max(maxLen, maxLen>0?k - maxLen:k);
                    //跳到下一行继续
                    k++;
                    continue;
                }

            }
            System.out.println(maxLen > 0 ? maxLen + 1 : maxLen);
        }
    }
}
